package com.graph.impl;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

import com.graph.base.GraphBase;
import com.graph.base.GraphInterface;
import com.graph.base.VertexInterface;
import com.graph.util.GraphFileUtils;

public class AlgorithmGraph extends GraphBase implements GraphInterface{
	/**
	 * 遗传算法迭代次数
	 */
	private Integer T1;
	public Integer getT1() {
		return T1;
	}
	public void setT1(Integer t1) {
		T1 = t1;
	}
	public Integer getT2() {
		return T2;
	}
	public void setT2(Integer t2) {
		T2 = t2;
	}

	public Integer getL() {
		return L;
	}

	public void setL(Integer l) {
		L = l;
	}

	public double getK() {
		return K;
	}

	public void setK(double k) {
		K = k;
	}
	/**
	 * 退火算法迭代次数
	 */
	private Integer T2;
	/**
	 * 退火算法每次迭代次数
	 */
	private Integer L;
	/**
	 * 退火系数
	 */
	private double K;
	/**
	 * 初始化染色体数量
	 */
	private Integer initNum;
	public Integer getInitNum() {
		return initNum;
	}

	public void setInitNum(Integer initNum) {
		this.initNum = initNum;
	}
    /**
     * 希望划分社区数量
     */
	private Integer communityNum;
	public Integer getCommunityNum() {
		return communityNum;
	}

	public void setCommunityNum(Integer communityNum) {
		this.communityNum = communityNum;
	}
	List<LinkedList<Integer>> chromoList=new LinkedList<LinkedList<Integer>>();
	/**
	 * @Description:TODO
	 * @param args
	 * @author: wujiang
	 * @throws Exception 
	 * @time:2017-2-27 上午10:20:11
	 */
	public static void main(String[] args) throws Exception {
		AlgorithmGraph obj=new AlgorithmGraph(200,3,".\\Data\\","graph2.txt");
		List<Set<VertexInterface>>  res=obj.findCommunity(100,1000,10,0.99);
		AlgorithmGraph obj1=new AlgorithmGraph(100,1000,10,0.99,200,3,".\\Data\\","graph2.txt");
//		ModularityAlgorithm obj=new ModularityAlgorithm(500,2,".\\Data\\","graph.txt");
//		List<List<VertexInterface<String>>>  res=obj.findCommunity(200,1000,10,0.99);
		
//		ModularityAlgorithm obj=new ModularityAlgorithm(500,3,".\\Data\\","graph.txt");
//		List<List<VertexInterface>>  res=obj.findCommunity(800,200,10,0.99);
//		
		for (Set<VertexInterface> vertexInterfaces : res) {
		for (VertexInterface vertexInterface : vertexInterfaces) {
			System.out.print(vertexInterface.getName()+"、");
		}
		System.out.println();
	   }
	}
	
	public AlgorithmGraph(Integer initNum,Integer communityNum,String dataPath,String fileName) {
		this.initNum=initNum;
		this.communityNum=communityNum;
		GraphFileUtils.getInstance().read(dataPath,fileName,this);
	}
	
	
	public AlgorithmGraph(int t1, int t2, int l, double k, int initNum, int communityNum,
			String dataPath, String fileName) {
		this.T1=t1;
		this.T2=t2;
		this.L=l;
		this.K=k;
		this.initNum=initNum;
		this.communityNum=communityNum;
		GraphFileUtils.getInstance().read(dataPath,fileName,this);
	}
	public 	List<Set<VertexInterface>> findCommunity(Integer T1,double T2,Integer L,double K) throws Exception{
		if(T1==null||L==null)
			throw new Exception("未初始化所需参数！");
		this.initChromosome(chromoList,this.initNum,this.communityNum);
		List<LinkedList<Integer>> chormoes=selection(chromoList);
		int j=0;
		int i=0;
		LinkedList<Integer> c1=null;
		LinkedList<Integer> c2=null;
		do{
	    j++;
		//geneticOperation(c1, c2);
		c1=new LinkedList<Integer>(chormoes.get(0));
		c2=new LinkedList<Integer>(chormoes.get(1));
		geneticOperation(c1, c2);
		LinkedList<Integer> g1=new LinkedList<Integer>(c1);
		LinkedList<Integer> g2=new LinkedList<Integer>(c2);
		localSearchProcedure1(g1,g2,T2,L,K);
		chormoes.add(g1);
		chormoes.add(g2);
		chormoes=selection(chormoes);
		System.out.println("-----"+j+"------");
		}while(j<T1);
		return getComunityBychromosome(chormoes.get(0));
	}
	
	private void initChromosome(
			List<LinkedList<Integer>> chromoList , Integer initNum,Integer communityNum) {
			if(initNum<=0){
				initNum=this.getNumberOfVertices()/2;
			} 
			LinkedList<VertexInterface> chromo=new LinkedList<VertexInterface>(getVerticesList());
			Integer size=chromo.size();
			Random rand = new Random();
			for (int i = 0; i < initNum; i++) {
				LinkedList<Integer> chromoTemp=new LinkedList<Integer>();
				chromoList.add(0, chromoTemp);
				for (int j = 0; j < size; j++) {
					Integer t=rand.nextInt(communityNum);
					chromoTemp.addFirst(t);
				}
			}
		}
	
	private void localSearchProcedure(LinkedList<Integer> g1,LinkedList<Integer> g2,double T,Integer L,double K){
		Boolean isSelected=false;
		Integer i=0;
		LinkedList<Integer> G1=null;
		LinkedList<Integer> G2=null;
		double P=0;
		do{
		do{
	    do{
		G1=new LinkedList<Integer>(g1);
		G2=new LinkedList<Integer>(g2);
		CrossoverOperation(G1,G2);
		double Q1=this.ModularityChromoQ(G1);
		double Q2=this.ModularityChromoQ(G2);
		P=Q1-Q2;
		i++;
		double r=Math.random();
		if(P>0||r<Math.exp((-1*P))/T){
			isSelected=true;
		}
		}while(!isSelected);
	   if(P<0){
		g1.clear();
	    g1.addAll(G1);
	   // System.out.println("SELECT:"+this.graph.modularityQ(G1));
	    }
	    }while(i<L);
		T=K*T;
	    }while(T>=0.001);
	}
	
	private double ModularityChromoQ(LinkedList<Integer> chromo) {
		List<VertexInterface> allvers=getVerticesList();
		Map<VertexInterface,Integer> VI=new LinkedHashMap<VertexInterface, Integer>();
		Integer verNum=allvers.size();
		for (int i = 0; i <verNum; i++) {
			Integer n=chromo.get(i);
			VertexInterface v=allvers.get(i);
			VI.put(v, n);
		}
		return modularityQ(VI);
	}
	private void localSearchProcedure1(LinkedList<Integer> g1,LinkedList<Integer> g2,double T,Integer L,double K){
		Boolean isSelected=false;
		Integer i=0;
		LinkedList<Integer> G1=null;
		LinkedList<Integer> G2=null;
		double P=0;
		do{
		do{
			double q1=ModularityChromoQ(g1);
	    do{
		G1=new LinkedList<Integer>(g1);
		G2=new LinkedList<Integer>(g2);
		CrossoverOperation(G1,G2);
		double Q1=ModularityChromoQ(G1);
		P=q1-Q1;
		i++;
		double r=Math.random();
		if(P<0||r<Math.exp((P))/T){
			isSelected=true;
		}
		}while(!isSelected);
	     if(P<0){
		g1.clear();
	    g1.addAll(G1);
	    //System.out.println("SELECT:"+this.graph.modularityQ(G1));
	    }
	    }while(i<L);
		T=K*T;
	    }while(T>=0.001);
	}
	
	public List<Set<VertexInterface>> getComunityBychromosome(LinkedList<Integer> chromo){
		List<Set<VertexInterface>> communitys=new LinkedList<Set<VertexInterface>>();
		for (int j = 0; j <communityNum; j++) {
			communitys.add(new HashSet<VertexInterface>());
		}
		List<VertexInterface> allvers=getVerticesList();
		for (int i = 0; i <chromo.size(); i++) {
			Integer n=chromo.get(i);
			Set<VertexInterface> co=communitys.get(n);
			VertexInterface v=allvers.get(i);
			if(co==null){
				co=new HashSet<VertexInterface>();
				co.add(v);
			}else{
				co.add(v);
			}
		}
		return communitys;
	}

	@SuppressWarnings("unchecked")
	private void geneticOperation(LinkedList<Integer> chromo1,LinkedList<Integer> chromo2){
		CrossoverOperation(chromo1,chromo2);
		MutationOperator(chromo1,chromo2);
	}
	
	private void CrossoverOperation(LinkedList<Integer> chromo1,LinkedList<Integer> chromo2){
		LinkedList<Integer> chromoT1=new LinkedList<Integer>(chromo1);
		LinkedList<Integer> chromoT2=new LinkedList<Integer>(chromo2);
		Random rand = new Random();
		Integer size=getNumberOfVertices();
		Integer rndN=rand.nextInt(size);
		Integer n1=chromoT1.get(rndN);
		Integer n2=chromoT2.get(rndN);
        for (int i = 0; i < size; i++) {
			Integer labe1=chromoT1.get(i);
			if(labe1.equals(n1)){
				chromo2.set(i, labe1);
			}
			Integer labe2=chromoT2.get(i);
			if(labe2.equals(n2)){
				chromo1.set(i, labe2);
			}
		}
	}
	
	private  void MutationOperator(LinkedList<Integer>... chromos){
		Random rand = new Random();
		Integer size=getNumberOfVertices();
		for (LinkedList<Integer> linkedList : chromos) {
			int s=rand.nextInt(size);
			Integer t=rand.nextInt(communityNum);
			linkedList.set(s, t);
		}
	} 
	
	private List<LinkedList<Integer>> selection(List<LinkedList<Integer>> list){
		Collections.sort(list,new Comparator<LinkedList<Integer>>(){  
            @Override  
            public int compare(LinkedList<Integer> b1, LinkedList<Integer> b2) { 
            	double q1=ModularityChromoQ(b1);
            	double q2=ModularityChromoQ(b2);
            	if(q1==q2){
            		return 0;
            	}
            	if(q1>q2){
            		return -1;
            	}else{
            		return 1;
            	}
            }  
              
        });
		List<LinkedList<Integer>> re=new LinkedList<LinkedList<Integer>>(list.subList(0, 2));
		System.out.println("Q-MAX:"+ModularityChromoQ(re.get(0)));
		return re;
	}
	 
//	public double modularityQ(List<Integer> chromo){
//		List<VertexInterface> allvers=getVerticesList();
//		Map<VertexInterface,Integer> VI=new LinkedHashMap<VertexInterface, Integer>();
//		Integer verNum=allvers.size();
//		for (int i = 0; i <verNum; i++) {
//			Integer n=chromo.get(i);
//			VertexInterface v=allvers.get(i);
//			VI.put(v, n);
//		}
//		double Q=0.0;
//		int M2=getNumberOfEdges();//双向边的总数
//		for (int i = 0; i < verNum; i++) {
//			for (int j = 0; j < verNum; j++) {
//				if(i!=j){
//					VertexInterface v1=allvers.get(i);
//					VertexInterface v2=allvers.get(j);
//					if(VI.get(v1).equals(VI.get(v2))){
//					 double de=v1.getDegree()*v2.getDegree();
//					  if(isNeighbor(v1,v2)){
//						  Q=Q+(1.0-(de/(double)M2));
//					  }else{
//						  Q-=de/M2;
//					  }
//					}
//				}
//			}
//		}
//		return Q/(M2);
//	}

	@Override
	public Set<VertexInterface> findCommunityByVertices(String ver) {
		return null;
	}

	@Override
	public List<Set<VertexInterface>> findAllCommunity() throws Exception {
		return findCommunity(getT1(), getT2(), getL(), getK());
	}
	@Override
	public List<VertexInterface> getBoundaryVertices() throws Exception {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int[][] initMatrix() throws Exception {
		return new int[0][];
	}

	@Override
	public double getPrecision() {
		return 0;
	}

	@Override
	public double getRecall() {
		return 0;
	}

	@Override
	public double getF1() {
		return 0;
	}
}
